The present invention relates to error correcting codes for the correction of double errors and the detection of triple and packaging errors in memory arrays.
A double error correcting and triple error detecting (DEC-TED) code can be constructed based on the well known BCH coding theory (see W. W. Peterson and E. J. Weldon, Jr., Error Correcting Codes, 1972, MIT Press). To do this, let o.sup.c be a primitive element of the finite field GF(2.sup.m), and n=2.sup.m -1. If an element of GF(2.sup.m) is then expressed as a binary m-tuple, a DEC-TED BCH code of length n can be defined as the code with the following parity check matrix: ##EQU1## The number of check bits .nu. and the number of data bits k for this code are 2m+1 and n-2m-1 respectively. If 128 data bits are to be protected by the code, it should be apparent that m must be 8 or larger. For m=8 there is a (255,238) DEC-TED BCH code with n=255, k=238, and .nu.=17.
BCH codes can be shortened to a desired length by deleting data bit columns from the parity check matrix of the code. Doing this, a (145,128) shortened code can be obtained from the (255,238) DEC-TED BCH code defined by the matrix H in (1).
The number of check bits may also be reduced in the code shortening process by properly choosing the data bit columns in the parity check matrix to be deleted. An article by the inventor on how to do this, entitled "On Shortened Finite Geometry Codes" appeared in the April 1972 issue of Information and Control beginning on page 216. To use techniques described in the article on the parity check matrix H of (1):
(1) Apply elementary row operations (see page 32, W. W. Peterson and E. J. Weldon, Jr., Error Correcting Codes, 1972, MIT Press) on the parity check matrix H. Let H.sub.1 be the matrix after the row operations, and V be a row vector of H.sub.1. PA0 (2) Delete from H.sub.1 the row vector V and the column vectors at positions corresponding to the 1's in V. The resulting matrix is the parity check matrix of a shortened DEC-TED code with 2m check bits.
If m is even, a row vector that contains 2.sup.m-1.sub.- 2.sup.m/2 -1 1's can always be found by applying elementary row operations on the matrix H. Applying the shortening scheme above, a DEC-TED code with k=2.sup.m-1 +2.sup.m/2, .nu.=2m can be constructed. If m is odd, a row vector that contains 2.sup.m-1 -2.sup.(m-1)/2 -1 1's can be found by applying elementary row operations on the matrix H. Thus, a DEC-TED code with k 2.sup.m-1 +2.sup.(m-1)/2, .nu.=2m can be constructed.